package week_07;

import week_04.SingleList;

public class CicleLinklList<T> {
    //记录头节点
    private Node head;
    private Node last;
    //记录链表长度
    private int N;


    /**
     * 节点类
     */
    private class Node {
        //data域
        Integer item;
        //next域
        Node next;

        Node before;

        public Node(Integer item, Node next, Node before) {
            this.item = item;
            this.next = next;
            this.before = before;
        }
    }

    /**
     * 构造函数，初始化链表
     */
    public CicleLinklList() {
//        初始化头节点
        this.last = new Node(null, null, null);
        this.head = new Node(null, last, null);
//        初始化链表长度
        this.N = 0;
    }

    /**
     * 清空链表
     */
    public void clear() {
        head.next = null;
        this.N = 0;
    }

    /**
     * @return 获取链表长度
     */
    public int length() {
        return N;
    }

    /**
     * 判断链表是否为空
     *
     * @return 返回Boolean值
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * 获取i位置的元素
     *
     * @param i 要查找的元素的位置
     * @return 要查找的元素的值
     */
    public Integer get(int i) {
        Node n = head.next;
        for (int index = 0; index < i; index++) {
            n = n.next;
        }
        return n.item;
    }

    /**
     * 向链表中插入元素
     *
     * @param item 要在链表尾部插入的节点
     */
    public void insert(Integer item) {
        Node n = head;
//        从头节点开始一直找到链表尾部
        while (n.next != last) {
            n = n.next;
        }
//        在找到链表末尾的时候创建一个新节点
        Node newNode = new Node(item, last, null);
        n.next = newNode;
        newNode.before = n;
        last.next = head;
        N++;
    }

    /**
     * 在指定位置插入元素
     *
     * @param i    要插入的节点的位置
     * @param item 要插入的数值
     */
    public void insert(int i, Integer item) {
        Node n = head;
//        找到要插入的位置的前一个节点
        for (int index = 0; index < i - 1; index++) {
            n = n.next;
        }
        Node cur = n.next;
//        为要插入的元素创建一个新节点
        Node newNode = new Node(item, cur, n);
        n.next = newNode;
        cur.before = newNode;
        N++;
    }

    /**
     * 删除链表i处的元素
     *
     * @param i 要删除的节点的位置
     */
    public void remove(int i) {
//        从头节点开始循环找到第i位置
        Node n = head;
//        i前面的一个节点
        for (int index = 0; index < i - 1; index++) {
            n = n.next;
        }
//        第i处节点
        Node cur = n.next;
//        i后面的那个节点
        Node after = cur.next;
        n.next = after;
        N--;
    }

    /**
     * @param index 开始报号的序列号
     * @param k     报到要出局的序列号
     */
    public void josephRing(int index, int k) {
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        while (length() > 1) {
            if (n.next == last) {
                n.next = head.next;
            }
            if (k == index){
                remove(index);
                index = 0;
            }
            index++;
        }
    }
}
